/**
 * Created with IntelliJ IDEA.
 * Description :
 * User: $ {USER}
 * Date: $ {YEAR}-$ {MONTH}一$ { DAY}
 * Time: ${ TIME}
 */

/**
 * 题目：删除链表中重复出现的元素
 * 思路：先遍历链表，将链表中出现的元素用一个数组统计出来，
 *      接着再次遍历链表，将出现次数大于0的全部尾插到新链表中，
 *      接着再将这个数组对应的值置为0即可
 */
public class Test {
    public ListNode deleteDuplicates(ListNode head) {
        // 遍历原链表统计每个元素出现的次数
        int[] count = new int[400]; // 注意申请的数组的大小
        ListNode cur = head;
        while (cur != null) {
            // 结点值可能为负数，因此得让其变为正数
            // 并且后面在使用时，也得注意
            count[cur.val+100]++;
            cur = cur.next;
        }
        // 开始创建新链表
        ListNode newHead = new ListNode(-1);
        ListNode newLast = newHead;
        cur = head;
        while (cur != null) {
            if (count[cur.val+100] > 0) {
                // 出现了这个元素，就尾插到新链表中
                newLast.next = cur;
                newLast = newLast.next;
                // 把这个元素出现的次数置为0
                count[cur.val+100] = 0;
            }
            cur = cur.next;
        }
        // 如果原链表的最后的节点为重复节点，那么就会导致继续遍历
        // 因此得把新链表的尾节点的next值置为空
        newLast.next = null;
        return newHead.next;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}
